package com.bondar.linkedhashset;

import java.util.Collection;
import java.util.Iterator;

import com.bondar.interfaces.Set;

public class MyLinkedHashSet<T> implements Set<T> {

	private SimpleEntry<T> head;
	private SimpleEntry<T>[] table;
	private int capacity;
	private double loadFactor;
	private int size;

	public MyLinkedHashSet(int capacity, double loadfactor) {
		this.loadFactor = loadfactor;
		this.capacity = capacity;
		head = new SimpleEntry<T>(-1, null, null);
		head.setAfter(head);
		head.setBefore(head);
		table = new SimpleEntry[capacity];
		size = 0;
	}

	public MyLinkedHashSet(int capacity) {
		this(capacity, .75);
	}

	public MyLinkedHashSet() {
		this(16, .75);
	}

	@Override
	public void add(T element) {

		if (contains(element)) {
			return;
		}

		// resize if set is full
		ensureCapacity();

		int hash = element == null ? 0 : element.hashCode();
		int index = hash & (table.length - 1);

		SimpleEntry<T> old = table[index];

		SimpleEntry<T> entry = new SimpleEntry<T>(hash, element, old);
		table[index] = entry;

		entry.addBefore(head);
		++size;
	}

	private void ensureCapacity() {
		if (size >= capacity * loadFactor) {
			resize(2 * capacity);
		}
	}

	private void resize(int capacity) {
		this.capacity = capacity;

		SimpleEntry<T>[] tmp = new SimpleEntry[capacity];

		for (int i = 0; i < table.length; i++) {

			SimpleEntry<T> newEntry;
			SimpleEntry<T> entry = table[i];

			while (entry != null) {

				SimpleEntry<T> next = entry.next;
				newEntry = entry;

				// recalculate new hashCode
				int hash = newEntry.getKey().hashCode();
				int index = hash & (tmp.length - 1);

				// add this element to the HEAD of list (entry)
				newEntry.next = tmp[index];
				tmp[index] = newEntry;
				entry = next;

			}
		}

		table = tmp;
	}

	@Override
	public Iterator<T> iterator() {
		return new Iterator<T>() {
			SimpleEntry<T> current = head;

			@Override
			public boolean hasNext() {
				return current != head.before;
			}

			@Override
			public T next() {
				return (current = current.getAfter()).getKey();
			}

			@Override
			public void remove() {
			}

		};
	}

	public boolean remove(T key) {
		int hash = key == null ? 0 : key.hashCode();
		int index = hash & (table.length - 1);

		SimpleEntry<T> entry = table[index];
		SimpleEntry<T> prev = table[index];

		for (; entry != null; entry = entry.next) {

			if (key == entry.key || (key != null && entry.getKey().equals(key))) {
				removeEntry(index, entry, prev);
				--size;
				return true;
			}

			prev = entry;
		}

		return false;
	}

	private void removeEntry(int index, SimpleEntry<T> entry,
			SimpleEntry<T> prev) {
		// is one element in the entry?
		if (entry == prev) {
			table[index] = null;
		} else {
			prev.next = entry.next;
			entry.remove();
		}
	}

	private static class SimpleEntry<T> {

		private T key;
		private SimpleEntry<T> next;
		private SimpleEntry<T> after;
		private SimpleEntry<T> before;
		private int hashCode;

		public SimpleEntry(int hash, T key, SimpleEntry<T> next) {
			this(hash, key, next, null, null);
		}

		public SimpleEntry(int hash, T key, SimpleEntry<T> next,
				SimpleEntry<T> after, SimpleEntry<T> before) {
			this.key = key;
			this.next = next;
			this.hashCode = hash;
			this.after = after;
			this.before = before;
		}

		public T getKey() {
			return key;
		}

		public SimpleEntry<T> getAfter() {
			return after;
		}

		public void setAfter(SimpleEntry<T> after) {
			this.after = after;
		}

		protected void addBefore(SimpleEntry<T> lastEntry) {
			after = lastEntry;
			before = lastEntry.before;
			before.after = this;
			after.before = this;
		}

		public void setBefore(SimpleEntry<T> before) {
			this.before = before;
		}

		public void remove() {
			before.after = after;
			after.before = before;
		}

		@SuppressWarnings("unchecked")
		@Override
		public boolean equals(Object obj) {
			if (obj == this) {
				return true;
			}
			if (!(obj instanceof SimpleEntry)) {
				return false;
			}

			SimpleEntry<T> se = (SimpleEntry<T>) obj;
			return (key == null ? se.key == null : key.equals(se.key));
		}

		@Override
		public int hashCode() {
			int result = hashCode;
			if (result == 0) {
				result = 17;
				result = 31 * result
						+ (this.key == null ? 0 : this.key.hashCode());
				hashCode = result;
			}

			return result;
		}

	}

	@Override
	public boolean contains(Collection<T> elements) {
		for (T element : elements) {
			if (!contains(element)) {
				return false;
			}
		}
		return true;
	}

	@Override
	public boolean contains(T element) {
		if (size == 0) {
			return false;
		}

		for (SimpleEntry<T> simpleEntry = head.after; simpleEntry != head; 
				simpleEntry = simpleEntry.after) {

			T key = simpleEntry.getKey();

			if (key == element || (key != null && key.equals(element))) {
				return true;
			}
		}
		return false;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {
		size = 0;

		for (int i = 0; i < table.length; i++) {
			table[i] = null;
		}
	}

}
